package net.projecteuler.prob;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;

public class Problem67 implements Runnable {
	
	int[][] triangle = null;
	private static final int SIZE = 100;

	@Override
	public void run() {
		getTriangle();
		
		int[] maxSum = new int[]{triangle[0][0]};
		for(int i = 1; i < SIZE; i++){
			int[] maxTemp = new int[i+1];
			maxTemp[0] = maxSum[0] + triangle[i][0];
			for(int j = 1; j <= i - 1; j++){
				maxTemp[j] = maxSum[j-1] > maxSum[j] ? maxSum[j-1] + triangle[i][j] : maxSum[j] + triangle[i][j];
			}
			maxTemp[i] = maxSum[i - 1] + triangle[i][i];
			maxSum = maxTemp;
		}
		
		int maxPath = 0;
		for(int i = 0; i < maxSum.length; i++ )
			if(maxSum[i] > maxPath)
				maxPath = maxSum[i];
		
		System.out.println(maxPath);
	}
	
	public void getTriangle(){
		try{
			File file = new File("./res/triangle.txt");
			BufferedReader bi = new BufferedReader(new FileReader(file));
			String line;
			
			triangle = new int[SIZE][];
			
			int idx = 0;
			while((line = bi.readLine()) != null){
				String[] numberStrs = line.split(" ");
				triangle[idx] = new int[numberStrs.length];
				for(int i = 0; i < numberStrs.length; i++)
					triangle[idx][i] = Integer.parseInt(numberStrs[i]);
				
				idx++;
			}
		} catch(Exception e) {
			e.printStackTrace();
			return;
		}
	}

}
